package LRU缓存淘汰;

import java.util.HashMap;

public class LRUCache {

    public HashMap<Integer, Node> map;
    public DoubleList cache;
    public int size;

    public LRUCache(int size) {
        this.map = new HashMap<>();
        this.cache = new DoubleList();
        this.size = size;
    }

    // put方法
    public void put(Node node) {
        // 判断是否存在
        if (map.containsKey(node.key)) {
            // 如果已经存在，先移除旧的
            remove(map.get(node.key));
        } else if (cache.capacity == size) {
            // 如果容量满了，移除头部最不常用的节点
            Node first = cache.removeFirst();
            map.remove(first.key);
        }
        // 插入新节点到链表末尾
        cache.addLast(node);
        map.put(node.key, node);
    }

    // get方法
    public Integer get(Integer key) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            // 将节点移到链表末尾
            remove(node);
            cache.addLast(node);
            return node.value;
        } else {
            return null;
        }
    }

    // 删除节点
    private void remove(Node node) {
        if (node.prev != null) {
            node.prev.next = node.next;
        }
        if (node.next != null) {
            node.next.prev = node.prev;
        }
        if (node == cache.tail) {
            cache.tail = node.prev;
        }
        if (node == cache.head.next) {
            cache.head.next = node.next;
        }
        cache.capacity--;
    }

    public static void main(String[] args) {
        Node node1 = new Node(1, 1);
        Node node2 = new Node(2, 2);
        Node node3 = new Node(3, 3);
        LRUCache cache = new LRUCache(2);
        cache.put(node1);
        cache.put(node2);
        cache.cache.printList();//12
        cache.get(node1.key);
        cache.cache.printList();//21
        cache.put(node3);
        cache.get(node3.key);// 输出null，因为node1被淘汰
        cache.cache.printList(); //13
    }
}
